翻訳と辞書 Words near each other ・ Iterated integral ・ Iterated limit ・ Iterated local search ・ Iterated logarithm ・ Iterated monodromy group ・ Iteratee ・ ITerating ・ Iteration ・ Iteration (disambiguation) ・ Iteration mark ・ Iterations of I ・ Iterative and incremental development ・ Iterative aspect ・ Iterative closest point ・ Iterative compression ・ Iterative deepening A* ・ Iterative deepening depth-first search ・ Iterative design ・ Iterative impedance ・ Iterative learning control ・ Iterative method ・ Iterative proportional fitting ・ Iterative Receiver Design ・ Iterative reconstruction ・ Iterative refinement ・ Iterative Template Library ・ Iterative Viterbi decoding ・ Iteratively reweighted least squares ・ Iterator ・ Iterator pattern Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Iterative deepening A* ： ウィキペディア英語版 Iterative deepening A* Iterative deepening A * (IDA *) is a graph traversal and path search algorithm that can find the shortest path between a designated start node and any member of a set of goal nodes in a weighted graph. It is a variant of iterative deepening depth-first search that borrows the idea to use a heuristic function to evaluate the remaining cost to get to the goal from the A * search algorithm. Since it is a depth-first search algorithm, its memory usage is lower than in A *, but unlike ordinary iterative deepening search, it concentrates on exploring the most promising nodes and thus doesn't go to the same depth everywhere in the search tree. Unlike A *, IDA * doesn't utilize dynamic programming and therefore often ends up exploring the same nodes many times. While the standard iterative deepening depth-first search uses search depth as the cutoff for each iteration, the IDA * uses the more informative $f(n)\; =\; g(n)\; +\; h(n)$ where $g(n)$ is the cost to travel from the root to node $n$ and $h(n)$ is a problem-specific heuristic estimate of the cost to travel from $n$ to the solution. As in A *, the heuristic has to have particular properties to guarantee optimality (shortest paths); see Properties, below. Applications of IDA * are found in such problems as planning. The algorithm was first described by Richard Korf in 1985. == Pseudocode == node ''current node'' g ''the cost to reach current node'' f ''estimated cost of the cheapest path (root..node..goal)'' h(node) ''estimated cost of the cheapest path (node..goal)'' cost(node, succ) ''path cost function'' is_goal(node) ''goal test'' successors(node) ''node expanding function'' procedure ida_star(root) bound := h(root) loop t := search(root, 0, bound) if t = FOUND then return FOUND if t = ∞ then return NOT_FOUND bound := t end loop end procedure function search(node, g, bound) f := g + h(node) if f > bound then return f if is_goal(node) then return FOUND min := ∞ for succ in successors(node) do t := search(succ, g + cost(node, succ), bound) if t = FOUND then return FOUND if t < min then min := t end for return min end function 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Iterative deepening A*」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.